Graph Neural Networks (GNN)
By Prof. Seungchul Lee
http://iai.postech.ac.kr/
Industrial AI Lab at POSTECH
http://iai.postech.ac.kr/
Industrial AI Lab at POSTECH
Table of Contents¶
1. Graph ¶
- Graphs G(V,E)
- V: a set of vertices (nodes)
- E: a set of edges (links, relations)
- weight (edge property)
- distance in a road network
- strength of connection in a personal network
- Graphs model any situation where you have objects and pairwise relations (symmetirc or asymmetirc) between the objects
| Vertex | Edge | |
|---|---|---|
| People | like each other | undirected |
| People | is the boss of | directed |
| Tasks | cannot be processed at the same time | undirected |
| Computers | have a direct network connection | undirected |
| Airports | planes flies between them | directed |
| City | can travel between them | directed |
1.1. Type of Graph ¶
Undirected Graph vs. Directed Graph
- Undirected graph
- Edges of undirected graph points both ways between nodes
- ex) Two-way road
- Directed graph
- A graph in which the edges are directed
- ex) One-way raod
Weighted Graph
- A graph with edges assigned costs or weights
- Also called 'Network'
- ex) connection between cities, length of road, circuit element capacity, communication network usage fee, etc.
Cycle vs. Acyclic Graph
- Cycle
- Simple path with start node and end node are same
- Simple Path: No repeating vertices in the path
- Simple path with start node and end node are same
- Acyclic Graph
- A graph without cycle
1.2. Graph Structure ¶
Graph and Adjacency Matrix
- Simple undirected graph consist of only nodes and edges
- Graph can be represented as adjacency matrix $A$
- Adjacency matrix $A$ indicates adjacent nodes for each node
- Need (number of nodes) $ \times$ (number of nodes) shape matirx to represent adjacency matirx of undirected graph
- Symmetirc matirx
2. Graph Neural Network ¶
- Machine learning techniques such as linear regression can be applied well in Euclidean space, conversely it is not good for non-Euclidean domains
- Machine learning models suppose that features are independent to each other, but in non-Euclidean domains such as tree or graph features are related to each other
- Graph Neural Network (GNN) is a method that can be applied to non-Euclidean domains
- GNN are classified into 4 classes
- Recurrent Graph Networks (RecGNNs)
- Convolutional Graph Neural Networks (ConvGNNs)
- Graph AutoENcoders (GAEs)
- Spatial-Temporal Graph Neural Networks (STGNNs)
3. Graph Convolution Network (GCN) ¶
3.1. Convolution ¶
- In previous CNN lecture CNN has two characteristics, preserving the spatial structure and weight sharing
- To apply convolution in graph network, graph also has to conpensate that characteristics too
Convolution Layer
- In CNN, convolution layer preserve the spatial structure of input
- It convolve over all spatial locations
- Extract features for each convolution layer
Weight Sharing
- Reduce the number of parameters by weight sharing
- Within the same layer, the same filter will be used throughout image
3.2. Connection between CNN and GCN ¶
- GCNs perform similar operations where the model learns the features by inspecting neighboring nodes
- The major difference between CNNs and GCNs is that CNNs are specially built to operate on regular (Euclidean) structured data, while GCNs operate for the graph data that the number of nodes connections vary and the nodes are unordered (irregular on non-Euclidean structured data)
3.3. Update Hidden States in GCN ¶
- Similar to CNN, GCN updates each node with their adjacent nodes
- Unlike CNN, each node of GCN has different number of adjacent nodes
- Indicate adjacent nodes of each node by adjacency matrix A
- Basic process (or terminology) of GNN
- Message: information passed by neighboring nodes to the central node
- Aggregate: collect information from neighboring nodes
- Update: embedding update by combining information from neighboring nodes and from itself
Update for Each Node
$$\begin{align*} H_1^{(l+1)} &= \sigma \left(H_1^{(l)}W^{(l)} + H_2^{(l)}W^{(l)} + H_3^{(l)}W^{(l)} + H_4^{(l)}W^{(l)} + b^{(l)} \right) \\ &= \sigma \left(\sum_{j \in N} H_j^{(l)}W^{(l)} + b^{(l)} \right) \\ \end{align*}$$
- $H_1^{(l)}$: feature matirx of first node in $l^{th}$ layer
- $W^{(l)}$: weight of $l^{th}$ layer
- Weight sharing: share same weight for each layer
- In the same layer, each node is updated similarly, so it shares the same weight
- weight sharing enchance computing complexity and time
- Weight sharing: share same weight for each layer
- For each layer, the feature matrix and weight matirx are multiplied to create the next featuere matrix
Matrix Computation for Each Layer
- Above image indicate matirx computation of feature matrix and weight matirx in each layer
- $(i,j)$ cell of output matrix indicate the value of applying the $j^{th}$ filter to the $i^{th}$ node
- Like convolution, extract high dimension information by applying filters for each layer
- By multiplying adjacency matirx A to output matrix, update only iwth the node information connected to each node
- Enables the model to learn the feature representations based on nodes connectivity
3.4. Readout - Permutation Invariance ¶
- Adjacency matrix can be different even though two graph has the same network structure
- Even if the edge information between all nodes is the same, the order of values in the matrix may be different due to rotation and symmetry
- Readout layer makes this permutation invariant by multiplying MLP
Node-wise summation
$$ Z_G = \tau \left(\sum_{i \in G} MLP \left(H_i^{(L)} \right) \right) $$3.5. Overall Structure of GCN ¶
- Graph information with feature matirx and adjacency matrix input to GCN
- Graph Convolution Layer
- Update information of each node according to their adjacency matirx
- Collect all node information with MLP and determine a certain value for regression or classification in Readout layer
3.6. Three Types of GNN Problem ¶
Task 1: Node classification
Task 2: Edges prediction
Task 3: Graph classification
4. Lab1: Building Simple Graph Convolutional Networks ¶
- Simple graph using 6 nodes
- Learn the nodes features representation by building GCN
In [2]:
# !pip install networkx
4.1. Initializing the graph G ¶
In [6]:
import networkx as nx
import numpy as np
import matplotlib.pyplot as plt
from scipy.linalg import fractional_matrix_power
%matplotlib inline
G = nx.Graph(name = 'G')
for i in range(6):
G.add_node(i, name = i)
edges = [(0, 1), (0, 2), (1, 2), (0, 3), (3, 4), (3, 5), (4, 5)]
G.add_edges_from(edges)
print('Graph Info:\n', nx.info(G))
print('\nGraph Nodes: ', G.nodes.data())
nx.draw(G, with_labels = True, font_weight = 'bold')
plt.show()
4.2. Insert adjacency matrix (A) to forward pass equation ¶
In [2]:
A = np.array(nx.attr_matrix(G, node_attr='name')[0])
X = np.array(nx.attr_matrix(G, node_attr='name')[1])
X = np.expand_dims(X, axis=1)
print('shape of A: ', A.shape)
print('\nShape of X: ', X.shape)
print('\nAdjacency Matirx (A):\n', A)
print('\nNode Features Matirx (X):\n', X)
In [3]:
AX = np.dot(A, X)
print("Dot product of A and X (AX):\n", AX)
4.3. Insert self-loops and normalizing A ¶
Degree of undirected graph
- the degree of vertex in a graph is the number of edges connected to it
- denote the degree of vertex $i$ by $d_i$
- for an undirected graph of $n$ vertices
- Degree matrix $D$ of $A$
- example
$$A = \begin{bmatrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{bmatrix} \qquad \Rightarrow \qquad D = \begin{bmatrix} 3 & 0 & 0 & 0 \\ 0 & 2 & 0 & 0 \\ 0 & 0 & 3 & 0 \\ 0 & 0 & 0 & 2 \end{bmatrix} $$
Normalized $\tilde A$
Adding $I$ is to add self-connecting edges
Considering neighboring nodes in the normalized weights
- to prevent numerical instabilities and vanishing/exploding gradients in order for the model to converge
Now we consider a feature matrix $X$
- Weighted sum (or averaging) of neighboring features
Message passing framework
- How a single node aggregates messages from its local neighborhood
Message passing with self-loops
- As a simplification of the neural message passing approach, it is common to add self-loops to the input graph and omit the explicit update step
Neighborhood normalization
The most basic neighborhood aggregation operation simply takes the sum of the neighbor embeddings. One issue with this approach is that it can be unstable and highly sensitive to node degrees.
One solution to this problem is to simply normalize the aggregation operation based upon the degrees of the nodes involved. The simplest approach is to just take an average rather than sum
Finally Graph Convolutional Networks
$$ \begin{align*} H^{(k+1)} &= \sigma \left( \left(\tilde D^{-1/2}(A+I)\tilde D^{-1/2} \right)H^{(k)} \, W^{(k)}\right)\\ &= \sigma \left( \tilde A H^{(k)} \, W^{(k)}\right) \end{align*} $$normalizing term = $D^{-1}AX$¶
In [4]:
G_self_loops = G.copy()
self_loops = []
for i in range(G.number_of_nodes()):
self_loops.append((i, i))
G_self_loops.add_edges_from(self_loops)
print('Edges of G with self-loops:\n', G_self_loops.edges)
A_hat = np.array(nx.attr_matrix(G_self_loops, node_attr='name')[0])
print('Adjacency Matrix of added self-loops G (A_hat):\n', A_hat)
AX = np.dot(A_hat, X)
print('AX:\n', AX)
In [5]:
Deg_Mat = G_self_loops.degree()
print('Degree Matrix of added self-loops G (D): ', Deg_Mat)
D = np.diag([deg for (n, deg) in list(Deg_Mat)])
print('Degree Matrix of added self-loops G as numpy array (D):\n', D)
D_inv = np.linalg.inv(D)
print('Inverse of D:\n', D_inv)
DAX = np.dot(D_inv, AX)
print('DAX:\n', DAX)
normalizing term = $D^{-1/2}AD^{-1/2}X$¶
In [6]:
D_half_norm = fractional_matrix_power(D, -0.5)
DADX = D_half_norm.dot(A_hat).dot(D_half_norm).dot(X)
print('DADX:\n', DADX)
4.4. Adding weights and activation function ¶
Adding a non-linear function: 1st layer
$$ \begin{align*} H &= f \left(X, \tilde A \right) \\ & = \sigma \left(\tilde A X \, W \right) \end{align*} $$Adding a non-linear function: $\mathcal l^{\text{th}}$ layer
$$ \begin{align*} H^{(\mathcal{l}+1)} &= f \left(H^{(\mathcal{l})}, \tilde A \right) \\ & = \sigma \left(\tilde A H^{(\mathcal{l})} \, W \right) \end{align*} $$In [7]:
np.random.seed(7777)
n_h = 4
n_y = 2
W0 = np.random.randn(X.shape[1], n_h) * 0.01
W1 = np.random.randn(n_h, n_y) * 0.01
def relu(x):
return np.maximum(0, x)
def gcn(A, H, W):
I = np.identity(A.shape[0])
A_hat = A + I
D = np.diag(np.sum(A_hat, axis=0))
D_half_norm = fractional_matrix_power(D, -0.5)
eq = D_half_norm.dot(A_hat).dot(D_half_norm).dot(H).dot(W)
return relu(eq)
H1 = gcn(A, X, W0)
H2 = gcn(A, H1, W1)
print('Features Representation from GCN output:\n', H2)
4.5. Plotting the features representation ¶
In [8]:
def plot_features(H2):
x = H2[:,0]
y = H2[:,1]
size = 1000
plt.scatter(x, y, size)
plt.xlim([np.min(x) * 0.9, np.max(x) * 1.1])
plt.ylim([-1, 1])
for i, row in enumerate(H2):
str = "{}".format(i)
plt.annotate(str, (row[0], row[1]), fontsize=18, fontweight='bold')
plt.show()
plot_features(H2)
5. Lab2: Node Classification using Graph Convolutional Networks ¶
In [6]:
#importing dependencies
import numpy as np
import os
import networkx as nx
from tensorflow.keras.utils import to_categorical
from sklearn.preprocessing import LabelEncoder
from sklearn.utils import shuffle
from sklearn.metrics import classification_report
from spektral.layers import GraphConv
from tensorflow.keras.models import Model
from tensorflow.keras.layers import Input, Dropout, Dense
from tensorflow.keras import Sequential
from tensorflow.keras.optimizers import Adam
from tensorflow.keras.callbacks import TensorBoard, EarlyStopping
import tensorflow as tf
from tensorflow.keras.regularizers import l2
from collections import Counter
from sklearn.manifold import TSNE
import matplotlib.pyplot as plt
5.1. Data loading ¶
In [5]:
labels = np.load('./data_files/cora_labels.npy')
nodes = np.load('./data_files/cora_nodes.npy')
edge_list = np.load('./data_files/cora_edges.npy')
X = np.load('./data_files/cora_features.npy')
N = X.shape[0]
F = X.shape[1]
print('X shape: ', X.shape)
print('\nNumber of nodes (N): ', N)
print('\nNumber of features (F) of each node: ', F)
print('\nCategories: ', set(labels))
num_classes = len(set(labels))
print('\nNumber of classes: ', num_classes)
5. 2 Train / Validation / Test data splitting¶
In case of GCN, it is possible to train with small number of data compared to supervised method because it is semi-supervised method. Therefore, in this task, train dataset will consist of 20 data for each class. Likewise, execute validation and test with 500 validation dataset and 1000 test dataset.
In [7]:
def encode_label(labels):
label_encoder = LabelEncoder()
labels = label_encoder.fit_transform(labels)
labels = to_categorical(labels)
return labels, label_encoder.classes_
labels_encoded, classes = encode_label(labels)
In [8]:
label_counter = np.zeros((num_classes, 1))
train_idx = []
for i in range(len(labels_encoded)):
label = np.argmax(labels_encoded[i])
if label_counter[label] < 20:
train_idx.append(i)
label_counter[label] += 1
rest_idx = [x for x in range(len(labels)) if x not in train_idx]
val_idx = rest_idx[:500]
test_idx = rest_idx[500:(500 + 1000)]
In [9]:
train_mask = np.zeros((N,), dtype=bool)
train_mask[train_idx] = True
val_mask = np.zeros((N,), dtype=bool)
val_mask[val_idx] = True
test_mask = np.zeros((N,), dtype=bool)
test_mask[test_idx] = True
In [10]:
print("All Data Distribution: \n{}".format(Counter(labels)))
print("\n")
print("Training Data Distribution: \n{}".format(Counter([labels[i] for i in train_idx])))
print("\n")
print("Validation Data Distribution: \n{}".format(Counter([labels[i] for i in val_idx])))
print("\n")
print("Test Data Distribution: \n{}".format(Counter([labels[i] for i in test_idx])))
5.3 Initializing the graph G¶
In [12]:
G = nx.Graph(name='Cora')
G.add_nodes_from(nodes)
G.add_edges_from(edge_list)
print('Graph info: ', nx.info(G))
5.4 Construct and Normalize adjacency matrix A¶
5.4.1 Insert self-loops to A¶
In [14]:
A = nx.adjacency_matrix(G)
I = np.eye(A.shape[-1], dtype=A.dtype)
A_hat = A + I
5.4.2 normalizing term = $D^{-1/2}AD^{-1/2}X$¶
In [17]:
degree = np.array(A_hat.sum(1))
D_half_norm = np.power(degree, -0.5).flatten()
D = np.diag(D_half_norm)
print('D:\n', D)
DAD = D.dot(A_hat).dot(D)
print('\nDAD:\n', DAD)
DAD = np.array(DAD, dtype=np.float32)
X = np.array(X, dtype=np.float32)
5.5 GCN Model¶
In [18]:
channels = 16
dropout = 0.5
l2_reg = 5e-4
learning_rate = 1e-2
epochs = 100
es_patience = 10
X_in = Input(shape=(F, ))
fltr_in = Input((N, ), sparse=True)
dropout_1 = Dropout(dropout)(X_in)
graph_conv_1 = GraphConv(channels,
activation='relu',
kernel_regularizer=l2(l2_reg),
use_bias=False)([dropout_1, fltr_in])
dropout_2 = Dropout(dropout)(graph_conv_1)
graph_conv_2 = GraphConv(num_classes,
activation='softmax',
use_bias=False)([dropout_2, fltr_in])
model = Model(inputs=[X_in, fltr_in], outputs=graph_conv_2)
optimizer = Adam(lr=learning_rate)
model.compile(optimizer=optimizer,
loss='categorical_crossentropy',
weighted_metrics=['acc'])
model.summary()
5.6 Train Model¶
In [19]:
validation_data = ([X, DAD], labels_encoded, val_mask)
model.fit([X, DAD],
labels_encoded,
sample_weight=train_mask,
epochs=epochs,
batch_size=N,
validation_data=validation_data,
shuffle=False,)
Out[19]:
5.7 Model Evaluation¶
In [20]:
from sklearn.metrics import confusion_matrix
import matplotlib.pyplot as plt
import numpy as np
def plot_confusion_matrix(y_true, y_pred, classes,
size=(10, 10),
fontsize=20,
cmap=plt.cm.Blues):
plt.rc('font', size = fontsize)
cm = confusion_matrix(y_true, y_pred)
fig, ax = plt.subplots(figsize=size)
im = ax.imshow(cm, interpolation='nearest', cmap=cmap)
ax.figure.colorbar(im, ax=ax, fraction=0.046, pad=0.04)
ax.set(xticks=np.arange(cm.shape[1]),
yticks=np.arange(cm.shape[0]),
xticklabels=classes, yticklabels=classes,
title='Confusion matrix for test dataset',
ylabel='True label',
xlabel='Predicted label')
plt.setp(ax.get_xticklabels(), rotation=45, ha="right", rotation_mode="anchor")
fmt = 'd'
thresh = cm.max() / 2.
for i in range(cm.shape[0]):
for j in range(cm.shape[1]):
ax.text(j, i, format(cm[i, j], fmt),
ha="center", va="center",
color="white" if cm[i, j] > thresh else "black", fontsize=20)
fig.tight_layout()
plt.show()
In [21]:
X_te = X[test_mask]
A_te = DAD[test_mask,:][:,test_mask]
y_te = labels_encoded[test_mask]
y_pred = model.predict([X_te, A_te], batch_size=N)
plot_confusion_matrix(np.argmax(y_te, axis=1), np.argmax(y_pred, axis=1), classes, fontsize=15)
5.8 T-SNE¶
In [22]:
layer_outputs = [layer.output for layer in model.layers]
activation_model = Model(inputs=model.input, outputs=layer_outputs)
activations = activation_model.predict([X,DAD],batch_size=N)
x_tsne = TSNE(n_components=2).fit_transform(activations[3])
In [23]:
def plot_tSNE(labels_encoded,x_tsne):
color_map = np.argmax(labels_encoded, axis=1)
plt.figure(figsize=(10,10))
for cl in range(num_classes):
indices = np.where(color_map==cl)
indices = indices[0]
plt.scatter(x_tsne[indices,0], x_tsne[indices, 1], label=cl)
plt.legend()
plt.show()
plot_tSNE(labels_encoded,x_tsne)
6. Useful Resources for Further Study ¶
In [1]:
%%html
<center><iframe src="https://www.youtube.com/embed/fOctJB4kVlM?rel=0"
width="560" height="315" frameborder="0" allowfullscreen></iframe></center>
In [2]:
%%html
<center><iframe src="https://www.youtube.com/embed/ABCGCf8cJOE?rel=0"
width="560" height="315" frameborder="0" allowfullscreen></iframe></center>
In [3]:
%%html
<center><iframe src="https://www.youtube.com/embed/0YLZXjMHA-8?rel=0"
width="560" height="315" frameborder="0" allowfullscreen></iframe></center>
In [4]:
%%html
<center><iframe src="https://www.youtube.com/embed/ex2qllcVneY?rel=0"
width="560" height="315" frameborder="0" allowfullscreen></iframe></center>
In [5]:
%%html
<center><iframe src="https://www.youtube.com/embed/YL1jGgcY78U?rel=0"
width="560" height="315" frameborder="0" allowfullscreen></iframe></center>
In [6]:
%%html
<center><iframe src="https://www.youtube.com/embed/8owQBFAHw7E?rel=0"
width="560" height="315" frameborder="0" allowfullscreen></iframe></center>
In [7]:
%%html
<center><iframe src="https://www.youtube.com/embed/R67-JxtOQzg?rel=0"
width="560" height="315" frameborder="0" allowfullscreen></iframe></center>
Libraries for TensorFlow: GraphNets, Spektral, DGL (or https://vermamachinelearning.github.io/keras-deep-graph-learning/)
University cources:
- COMP766 at McGill (https://cs.mcgill.ca/~wlh/comp766/)
- Alelab Alelab (https://www.youtube.com/channel/UC_YPrqpiEqkeGOG1TCt0giQ/playlists)
In [1]:
%%javascript
$.getScript('https://kmahelona.github.io/ipython_notebook_goodies/ipython_notebook_toc.js')